// lightbulbs.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <vector>
#include <string>
#include <iostream>
using namespace std;



// The function decimals2binarys will generate a binary string based on the input decimal string
// sample input      sample output
// "16"              "10000"
// "3"               "11"
// "12"              "1100"
// "1025"            "10000000001"
// Please note that the dec_str could be as long as 100 decimal digits, so the routine should be
// generic enough to handle very long strings.

string decimals2binarys(string dec_str)
{
	string binary_s;
	size_t next = 0;
	size_t et = dec_str.size();
	do {
		int r = 0;
		size_t st = next;
		while (st < et)
		{
			int d = 0;
			d = r * 10 + dec_str[st]-'0';
			r = d%2;
			d = d/2;
			dec_str[st++] = d+'0';
		}
		binary_s.insert(binary_s.begin(),r+'0');
		while(next<et&&dec_str[next]=='0')
			next++;
	} while(next<et);
	return binary_s;
}


// The function binarys2hexs will convert a binary string to a hexical string.
// sample input             sample output
// "1011"                   "B"
// "10000"                  "10"
// "11010"                  "1A"
// "101010001111"           "A8F"
string binarys2hexs(string bstr)
{
	string hexs;
	size_t et = bstr.size();
	while(et>0)
	{
		size_t st;
		if (et<4)
			st = 0;
		else
			st = et-4;
		int d=0;
		for (size_t i=st; i<et; i++)
			d = d*2+bstr[i]-'0';
		char h;
		if (d<10)
			h = '0'+d;
		else
			h = 'A'+d-10;
		hexs.insert(hexs.begin(),h);
		et = st;
	}
	return hexs;
}

// The hexs2decimals function will convert hexical string to decimal string with equal value
// Sample input (input hex string)                              Sample output (return string)
// "FF"                                                         "255"
// "FFEE"                                                       "65518"
// "FFFF"                                                       "65535"
// "10"                                                         "16"
string hexs2decimals(string hexs)
{
	string decimal_s;
	size_t next = 0;
	size_t et = hexs.size();

	do {
		int r = 0;
		size_t st = next;
		while (st < et)
		{
			int d = 0;
			d = r * 16 + (hexs[st]>='0'&&hexs[st]<='9'?(hexs[st]-'0'):(10+hexs[st]-'A'));
			r = d%10;
			d = d/10;
			hexs[st++] = (d>=0&&d<=9)?(d+'0'):('A'+d-10);
		}
		char c=r+'0';
		decimal_s.insert(decimal_s.begin(),c);
		while(next<et&&hexs[next]=='0')
			next++;
	} while(next<et);
	return decimal_s;
}

// The function binarys2decimals will generate a decimal string based on the input binary string
// sample input      sample output
// "10000"           "16"
// "11"              "3"              
// "1100"            "12"
// "10000000001"     "1025"
string binarys2decimals(string binary_str)
{
	return hexs2decimals(binarys2hexs(binary_str));
}

// xor_char implements XOR on two chars represent 0 and 1
// sample input          sample output
// 0 0                   0
// 0 1                   1
// 1 0                   1
// 1 1                   0
inline char xor_char(char c1, char c2)
{
	return (c1==c2)?'0':'1';
}

// xor_bstr implements XOR on two binary strings
// sample input          sample output
// 1001       1          1000
// 1010      11          1001
// 1100    1011          0111
// 1111     111          1000
string xor_bstr(string &op1, string &op2)
{
	string s;

	string::reverse_iterator it1=op1.rbegin(), it2=op2.rbegin();
	for(; it1!=op1.rend()&&it2!=op2.rend(); it1++, it2++)
		s.insert(s.begin(), xor_char(*it1,*it2));
	if(it1!=op1.rend())
	{
		for(;it1!=op1.rend();it1++)
			s.insert(s.begin(), *it1);
	}
	else if(it2!=op2.rend())
	{
		for(;it2!=op2.rend();it2++)
			s.insert(s.begin(), *it2);
	}
	return s;
}

// flipchar implements flip operation on 0 and 1 represented by char
// sample input     sample output
//            1     0
//            0     1
inline char flipchar(char c)
{
	return (c=='0')?'1':'0';
}

// calculate the cost of a solution i.e. number of '1' in a binary string
// sample input                sample output
// 1001000                     2
// 0010000                     1
// 1110000                     3
int costof(string switches)
{
	int cost = 0;

	for (size_t t = 0; t<switches.size(); t++)
		if (switches[t]=='1')
			++cost;
	return cost;
}

// search_solution function will start constructing with a partial solution described 
// by:
// diff_stat -- difference state upon which the solution will apply
// prev -- with any pre[i] is the state of i after applying solution[i-1] 
//         and solution[i] upon diff_stat
// solution -- light switches
// current_idx -- current light bulb state to consider
// startswitch -- '0' or '1' to indicate ON or OFF switch to try 
//
bool search_solution(const string &diff_stat, string &prev, string &solution,
	size_t &current_idx, char startswitch)
{
	size_t first_idx = current_idx;
	while(current_idx<solution.size())
	{
		if (current_idx==0)
		{
			if (startswitch=='0')
			{
				solution[current_idx] = '0';
				prev[current_idx] = diff_stat[current_idx];
			}
			else
			{
				solution[current_idx] = '1';
				prev[current_idx] = flipchar(diff_stat[current_idx]);
			}
		}
		else
		{
			if (prev[current_idx-1]=='0')
			{
				if (current_idx==first_idx&&startswitch=='1') //start with '1', violate last bit state
					return false;
				solution[current_idx] = '0'; //current switch off
				prev[current_idx] = (solution[current_idx-1]=='0')?diff_stat[current_idx]:
					flipchar(diff_stat[current_idx]); //flip by last switch
			}
			else // prev[current_idx-1]=='1'
			{
				solution[current_idx] = '1';
				prev[current_idx] = (solution[current_idx-1]=='1')?diff_stat[current_idx]:
					flipchar(diff_stat[current_idx]);
			}
		}
		current_idx++;
	}
	return prev[current_idx-1]=='0';
}

// lightbulbs function will search for solution of minimal cost based on the initial
// state, final state, and print the result with case number.
void lightbulbs(string init_stat, string final_stat, int caseno)
{
	init_stat = decimals2binarys(init_stat);
	final_stat = decimals2binarys(final_stat);

	string diff_stat = xor_bstr(init_stat,final_stat);

	//our goal is to change diff_stat to 0 by applying the light switches
	string	minimalcost_solution;
	int		mincost;
	string solution(diff_stat.size(),'0');
	string prev(diff_stat.size(),'0');
	size_t current_idx = 0;
	char   startswitch = '0';
	//backtracking
	do {
		bool res = search_solution(diff_stat, prev, solution, current_idx, startswitch);
		if (res==true)
		{ 
			if (minimalcost_solution.size()==0)
			{
				minimalcost_solution = solution;
				mincost = costof(solution);
			}
			else
			{
				if (costof(solution)<mincost)
				{
					minimalcost_solution = solution;
					mincost = costof(solution);
				}
			}
		}
		//backtracking
		while(current_idx>0&&solution[current_idx-1]=='1')
			current_idx--;
		if (current_idx==0)
		{	//no more solution
			break;
		}
		--current_idx;
		startswitch = '1';
	}while(1);
	if (minimalcost_solution.size()>0)
		cout<<"Case Number "<<caseno<<": "<<binarys2decimals(minimalcost_solution)<<endl;
	else
		cout<<"Case Number "<<caseno<<": impossible"<<endl;

}

// lightbulbs_solver() will first read in all pairs of initial/final states. It will try to solve
// each pair of initial/final state by calling lightbulbs function, which will find a minimal cost
// solution that consists of a string of ON/OFF switches. By applying the solution to the light bulbs
// with the initial state, those light bulbs will turn into the final state. 
// If a solution does not exist for a pair of initial/final state, lightbulbs function will print "impossible"
// with the case number.
void lightbulbs_solver()
{
	vector<string> init_stats;
	vector<string> final_stats;

	string init_s, final_s;
	do
	{
		cin>>init_s;
		cin>>final_s;
		if (init_s!="0"||final_s!="0")
		{
			init_stats.push_back(init_s);
			final_stats.push_back(final_s);
		}
		else
			break;
	} while(1);
	for (size_t t=0; t<init_stats.size(); t++)
	{
		if (t!=0) 
			cout<<endl; //print blank line between cases
		lightbulbs(init_stats[t], final_stats[t], (int)t+1);
	}
}



int main()
{
	lightbulbs_solver();
	return 0;
}

